package com.lfg.leetcode.leetcode300;

public class No309maxProfit {
    public static void main(String[] args) {
        int ret = maxProfit(new int[]{1, 2, 3, 0, 2});
        System.out.println("[" + ret + "]");
    }

    public static int maxProfit(int[] prices) {
        if (prices.length == 1) {
            return 0;
        }
        int b = -prices[0];
        int s = 0;
        int w = 0;

        for (int i = 1; i < prices.length; i++) {
            int b2 = Math.max(b, w - prices[i]);
            int s2 = b + prices[i];
            int w2 = Math.max(w, s);

            b = b2;
            s = s2;
            w = w2;
        }

        return Math.max(s, w);
    }

    public static int maxProfit2(int[] prices) {
        if (prices.length == 1) {
            return 0;
        }
        int[][] dp = new int[prices.length][3];
        dp[0][0] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][0]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
        }

        return Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2]);
    }
}
